|
In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language. John C. Reynolds gives a detailed account of the numerous discoveries of continuations.〔 〕 A function written in continuation-passing style takes an extra argument: an explicit "continuation" i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller. Programs can be automatically transformed from direct style to CPS. Functional and logic compilers often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (SSA). SSA is formally equivalent to a subset of CPS (excluding non-local control flow, which does not occur when CPS is used as intermediate representation).〔 * 〕 Functional compilers can also use A-normal form (ANF) (but only for languages requiring eager evaluation), rather than with 'thunks' (described in the examples below) in CPS. CPS is used more frequently by compilers than by programmers as a local or global style. ==Examples== In CPS, each procedure takes an extra argument representing what should be done with the result the function is calculating. This, along with a restrictive style prohibiting a variety of constructs usually available, is used to expose the semantics of programs, making them easier to analyze. This style also makes it easy to express unusual control structures, like catch/throw or other non-local transfers of control. The key to CPS is to remember that (a) ''every'' function takes an extra argument, its continuation, and (b) every argument in a function call must be either a variable or a lambda expression (not a more complex expression). This has the effect of turning expressions "inside-out" because the innermost parts of the expression must be evaluated first, so CPS explicates the order of evaluation as well as the control flow. Some examples of code in direct style and the corresponding CPS appear below. These examples are written in the Scheme programming language; by convention the continuation function is represented as a parameter named " k":Note that in the CPS versions, the primitives used, like +& and (define ( *& x y k) (k ( * x y))) (define (cps-prim f) (lambda args (let ((r (reverse args))) ((car r) (apply f (reverse (cdr r))))))) (define *& (cps-prim *)) (define +& (cps-prim +)) In order to call a procedure written in CPS from a procedure written in direct style, it is necessary to provide a continuation that will receive the result computed by the CPS procedure. In the example above (assuming that CPS-style primitives have been provided), we might call (factorial& 10 (lambda (x) (display x) (newline))).There is some variety between compilers in the way primitive functions are provided in CPS. Above we have used the simplest convention, however sometimes boolean primitives are provided that take two thunks to be called in the two possible cases, so the (=& n 0 (lambda (b) (if b ...))) call inside f-aux& definition above would be written instead as (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). Similarly, sometimes the if primitive itself is not included in CPS, and instead a function if& is provided which takes three arguments: a boolean condition and the two thunks corresponding to the two arms of the conditional.The translations shown above show that CPS is a global transformation. The direct-style ''factorial'' takes, as might be expected, a single argument; the CPS ''factorial&'' takes two: the argument and a continuation. Any function calling a CPS-ed function must either provide a new continuation or pass its own; any calls from a CPS-ed function to a non-CPS function will use implicit continuations. Thus, to ensure the total absence of a function stack, the entire program must be in CPS. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Continuation-passing style」の詳細全文を読む スポンサード リンク
|